| 翻訳と辞書 |
| Bitonic tour ： ウィキペディア英語版 |
Bitonic tour
In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice.
==Optimal bitonic tours==
The optimal bitonic tour is a bitonic tour of minimum total length. It is a standard exercise in dynamic programming to devise a polynomial time algorithm that constructs the optimal bitonic tour.〔''Introduction to Algorithms'', 3rd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2009. Problem 15-3, p. 405.〕〔.〕
The problem of constructing optimal bitonic tours is often credited to Jon L. Bentley, who published in 1990 an experimental comparison of many heuristics for the traveling salesman problem;〔.〕 however, Bentley's experiments do not include bitonic tours. The first publication that describes the bitonic tour problem appears to be a different 1990 publication, the first edition of the textbook ''Introduction to Algorithms'' by Thomas H. Cormen, Charles E. Leiserson, and Ron Rivest, which lists Bentley as the originator of the problem.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Bitonic tour」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|